﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.ListNode.ExchangeElement
{
    public class ListNode
    {
        public int val;
        public ListNode next;
        public ListNode(int val = 0, ListNode next = null)
        {
            this.val = val;
            this.next = next;
        }
    }

    //=============================== 力扣24 两两交换链表中的节点
    //给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
    //你不能只是单纯改变节点内的值，而是需要实际的进行节点交换。
    class ExchangeElement
    {
        // ================== 虚拟头节点方法
        public ListNode SwapPairs(ListNode head)
        {
            ListNode dummyHead = new ListNode(0);//设置虚拟头结点
            dummyHead.next = head;//将虚拟头结点指向head，方便后面做删除操作
            ListNode cur = dummyHead;
            while(cur.next != null && cur.next.next != null)
            {
                ListNode tmp = cur.next;//记录临时节点
                ListNode tmp1 = cur.next.next.next;//记录临时节点

                //进行两两交换
                cur.next = cur.next.next;
                cur.next.next = tmp;
                cur.next.next.next = tmp1;

                cur = cur.next.next;//cur移动两位，准备下一轮交换
            }
            return dummyHead.next;
        }
        //======================= 递归方法
        public ListNode SwapPairs_2(ListNode head )
        {
            if (head == null || head.next == null)
                return head;
            ListNode next = head.next;//获取当前节点的下一个节点
            ListNode newNode = SwapPairs_2(next.next);//进行递归

            //交换
            next.next = head;
            head.next = newNode;
            return next;
        }
    }
}
